package leetcode.to300;

import org.junit.Test;

public class T0034 {
    public int[] searchRange(int[] nums, int target) {
        int[] res=new int[]{-1,-1};
        if(nums==null||nums.length==0)
            return res;
        if(nums.length==1&&nums[0]!=target)
            return res;

        int left=0;
        int right=nums.length-1;

        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                //左边有相同值，说明第一个位置在mid左边，right=mid-1
                if(mid-1>=left&&nums[mid-1]==nums[mid]){
                    right=mid-1;
                }
                //左边无相同值，说明这就是第一个位置，找到了，退出循环
                else{
                    res[0]=mid;
                    break;
                }
            }
            else if(nums[mid]>target){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
        }

        left=res[0];//把左边界的值设为left，这样范围小点
        right=nums.length-1;

        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                //右边有相同值，说明最后一个位置在右边，left=mid+1
                if(mid+1<=right&&nums[mid+1]==nums[mid]){
                    left=mid+1;
                }
                //右边无相同值，说明这就是最后一个位置，找到了，退出循环
                else{
                    res[1]=mid;
                    break;
                }
            }
            else if(nums[mid]>target){
                right=mid-1;//在[2,2]，target=1的示例中，right=-1，而且没有索引检查，回出现数组越界异常。
            }
            else{
                left=mid+1;
            }
        }
        return res;
    }
    @Test
    public void test(){
        int[] nums=new int[]{2,2};
        searchRange(nums,1);
    }
    //进行index索引检查，防止数组索引越界。
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            int leftIdx = binarySearch(nums, target, true);
            int rightIdx = binarySearch(nums, target, false) - 1;
            if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
                return new int[]{leftIdx, rightIdx};
            }
            return new int[]{-1, -1};
        }

        public int binarySearch(int[] nums, int target, boolean lower) {
            int left = 0, right = nums.length - 1, ans = nums.length;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[mid] > target || (lower && nums[mid] >= target)) {
                    right = mid - 1;
                    ans = mid;
                } else {
                    left = mid + 1;
                }
            }
            return ans;
        }
    }

}
